﻿#region MIT
/*
Engine Of Evermore (http://code.google.com/p/engineofevermore/)
Copyright (c) 2008 Michael Woerister

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/
#endregion

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Drawing;
using System.Drawing.Imaging;
using System.Diagnostics;
using System.Xml.Linq;
using System.ComponentModel;
using System.Reflection;
using GorgonLibrary.Internal;
using GorgonLibrary.Graphics;
using Blue.ResourceManager;
using Green.Logging;
using EngineOfEvermore.Common;

namespace EngineOfEvermore.Imaging
{
    public class ImageMapException : Exception
    {
        public ImageMapException() 
        {}

        public ImageMapException( String message ) :
            base( message )
        {}

        public ImageMapException( String message, Exception inner ) :
            base( message, inner )
        {}
    }

    public class ImageMap : DisposableResource
    {
        #region IFrameGenerator Interface
        public interface IFrameGenerator
        {
            /// <summary>
            /// Returns a human-readable directoryName for the frame generator.
            /// </summary>
            String FriendlyName { get; }

            /// <summary>
            /// Returns the xml directoryName for this instance.
            /// </summary>
            String XmlName { get; }

            /// <summary>
            /// Generates the frames for the given sourceBitmap.
            /// </summary>
            IEnumerable<Rectangle> GenerateFrames( Bitmap sourceBitmap );

            /// <summary>
            /// Returns an XML Representation of the frame generator.
            /// </summary>
            /// <remarks>
            /// Must return an "FrameGenerator"-element with a "type" attribute that 
            /// states the type of the generator.
            /// This is a readonly property.
            /// </remarks>
            XElement XmlRepresentation { get; }

            /// <summary>
            /// Loads the data from the xml-rep.
            /// </summary>
            void LoadFromXmlRepresentation( XElement e );
        }
        #endregion

        #region Frame Class
        class Frame
        {
            public bool IsEmpty;
            public GorgonLibrary.Graphics.Image Image;
            public Rectangle OriginalArea;
            public Rectangle OriginalNonTransparentArea;
            public Rectangle ConvertedArea;
            public RectangleF TexCoords;
            public Point Offset;
            public Vector2d RelativeSize;
            public Vector2d RelativeOffset;
        }
        #endregion

        #region Variables
        IFrameGenerator _frameGenerator;
        bool _disposed;
        List<Frame> _frames;
        String _imageName;
        Size _atlasSize;
        GorgonLibrary.Graphics.Image _texture;
        #endregion

        #region Properties
        /// <summary>
        /// The Resource Name of the image to use.
        /// </summary>
        public String ImageName 
        {
            get { return _imageName; }
            private set { _imageName = value; }
        }

        public IFrameGenerator FrameGenerator
        {
            get { return _frameGenerator; }
            private set { _frameGenerator = value; }
        }

        public int FrameCount
        {
            get { return _frames.Count; }
        }
        #endregion

        #region Constructor
        private ImageMap( String name ):
            base( name )
        {

        }
        #endregion

        #region Methods
        public Size GetFrameSize( int frameIndex )
        {
            return _frames[frameIndex].OriginalArea.Size;
        }


        public int FindFrameAtPosition( Point position )
        {
            for ( int i = 0; i < _frames.Count; ++i )
            {
                if ( _frames[i].OriginalArea.Contains( position ) )
                {
                    return i;
                }
            }

            return -1;
        }

        public static void LoadFromXmlStream(
            Stream stream,
            out IFrameGenerator frameGenerator,
            out String imageName,
            out Size? sizeHint )
        {
            var sizeConverter = TypeDescriptor.GetConverter( typeof( Size ) );

            Debug.Assert( sizeConverter.CanConvertFrom( typeof( String ) ) );

            XDocument doc = XDocument.Load( new StreamReader( stream ) );

            imageName = (String) ( doc.Descendants( "ImageName" ).Single() );
            imageName = ResourceManager.NormalizeName( imageName );

            sizeHint = null;

            XElement atlasSizeElement =
                doc.Descendants( "AtlasSizeHint" ).SingleOrDefault();

            if ( atlasSizeElement != null )
            {
                sizeHint = (Size) sizeConverter.ConvertFromString( atlasSizeElement.Value );
            }

            XElement frameGeneratorElement = doc.Descendants( "FrameGenerator" ).Single();
            String frameGeneratorXmlName = frameGeneratorElement.Attribute( "type" ).Value;

            frameGenerator =
                ImageMap.CreateFrameGenerator( frameGeneratorXmlName );

            frameGenerator.LoadFromXmlRepresentation( frameGeneratorElement );
        }

        public static ImageMap LoadFromXmlStream( String resourceName, Stream stream )
        {
            Size? sizeHint;
            String imageName;
            IFrameGenerator frameGenerator;

            LoadFromXmlStream( stream, out frameGenerator, out imageName, out sizeHint );

            ImageMap imageMap = new ImageMap( resourceName );
            imageMap.ImageName = imageName;
            imageMap.FrameGenerator = frameGenerator;

            using ( Stream imageStream = ResourceManager.OpenStream( imageName, ResourceOpenMode.Read ) )
            {
                using ( Bitmap bitmap = new Bitmap( imageStream ) )
                {
                    imageMap._packImage( 
                        bitmap, 
                        frameGenerator.GenerateFrames( bitmap ), 
                        sizeHint 
                        );
                }
            }

            return imageMap;
        }

        public static void SaveAsResource( 
            String resourceName,
            IFrameGenerator frameGenerator,
            String imageName,
            Size? sizeHint )
        {
            Debug.Assert( frameGenerator != null );
            Debug.Assert( ResourceManager.ResourceExists( imageName ) );

            ImageMap imageMap = new ImageMap( resourceName );
            imageMap.ImageName = imageName;
            imageMap.FrameGenerator = frameGenerator;

            if ( sizeHint.HasValue )
            {
                imageMap._atlasSize = sizeHint.Value;
            }
            else
            {
                using ( Stream stream = ResourceManager.OpenStream( imageName, ResourceOpenMode.Read ) )
                {
                    using ( Bitmap bitmap = new Bitmap( stream ) )
                    {
                        List<Frame> frames = new List<Frame>();

                        ImageMap._findTransparentAreas( bitmap,
                            frameGenerator.GenerateFrames( bitmap ),
                            frames
                            );

                        imageMap._atlasSize = ImageMap._calculateSize( frames );
                    }
                }
            }

            if ( ResourceManager.ResourceExists( resourceName ) )
            {
                using ( Stream stream = ResourceManager.OpenStream(
                    resourceName, ResourceOpenMode.TruncateAndWrite ) )
                {
                    imageMap.SaveToXmlStream( stream );
                }
            }
            else
            {
                using ( Stream stream = ResourceManager.CreateResource( resourceName ) )
                {
                    imageMap.SaveToXmlStream( stream );
                }
            }
        }

        public void SaveToXmlStream( Stream stream )
        {
            var sizeConverter = TypeDescriptor.GetConverter( typeof( Size ) );
            Debug.Assert( sizeConverter.CanConvertFrom( typeof( String ) ) );

            Debug.Assert( _frameGenerator != null );

            XDocument doc = new XDocument(
                new XDeclaration( "1.0", "UTF-8", "yes" ),
                new XElement( "ImageMap",
                    new XElement( "ImageName", _imageName ),
                    new XElement( "AtlasSizeHint", 
                        sizeConverter.ConvertToString( _atlasSize ) ),
                    _frameGenerator.XmlRepresentation
                    )
            );

            using ( TextWriter textWriter = new StreamWriter( stream, Encoding.UTF8 ) )
            {
                doc.Save( textWriter );
            }
        }

        public void SetTextureActive( int frameIndex )
        {
            SlimRenderer.Instance.Image = _frames[frameIndex].Image;
        }

        /// <summary>
        /// Writes position and texcoord data to the given vertices.
        /// </summary>
        /// <param name="frameIndex">The index of the frame to draw.</param>
        /// <param name="position">The world coordinate position of the frame.</param>
        /// <param name="outArrayStartIndex">First array index that will be written to.</param>
        /// <param name="outArray">An array containing vertices to be written to.</param>
        public void DrawFrame( int frameIndex, RectangleF position, bool flipX, bool flipY,
            int outArrayStartIndex, VertexTypeList.PositionDiffuse2DTexture1[] outArray )
        {
            Frame frame = _frames[frameIndex];
            
            if ( frame.IsEmpty )
                return;

            if ( !flipX )
            {
                position.X += frame.RelativeOffset.X * position.Width;
                position.Width *= frame.RelativeSize.X;
            }
            else 
            {
                position.X += position.Width - frame.RelativeOffset.X * position.Width;
                position.Width *= -frame.RelativeSize.X;
            }

            if ( !flipY )
            {
                position.Y += frame.RelativeOffset.Y * position.Height;
                position.Height *= frame.RelativeSize.Y;
            }
            else
            {
                position.Y += position.Height - frame.RelativeOffset.Y * position.Height;
                position.Height *= -frame.RelativeSize.Y;
            }

            int outIndex = outArrayStartIndex;
            outArray[outIndex].Position.X = position.X;
            outArray[outIndex].Position.Y = position.Y;
            outArray[outIndex].TextureCoordinates.X = frame.TexCoords.Left;
            outArray[outIndex].TextureCoordinates.Y = frame.TexCoords.Top;

            ++outIndex;

            outArray[outIndex].Position.X = position.X + position.Width;
            outArray[outIndex].Position.Y = position.Y;
            outArray[outIndex].TextureCoordinates.X = frame.TexCoords.Right;
            outArray[outIndex].TextureCoordinates.Y = frame.TexCoords.Top;

            ++outIndex;

            outArray[outIndex].Position.X = position.X + position.Width;
            outArray[outIndex].Position.Y = position.Y + position.Height;
            outArray[outIndex].TextureCoordinates.X = frame.TexCoords.Right;
            outArray[outIndex].TextureCoordinates.Y = frame.TexCoords.Bottom;

            ++outIndex;

            outArray[outIndex].Position.X = position.X;
            outArray[outIndex].Position.Y = position.Y + position.Height;
            outArray[outIndex].TextureCoordinates.X = frame.TexCoords.Left;
            outArray[outIndex].TextureCoordinates.Y = frame.TexCoords.Bottom;
        }

        /// <summary>
        /// Writes position and texcoord data to the given vertices.
        /// </summary>
        /// <param name="frameIndex">The index of the frame to draw.</param>
        /// <param name="position">An array containing the 4 world vertex-positions.</param>
        /// <param name="outArrayStartIndex">First array index that will be written to.</param>
        /// <param name="outArray">An array containing vertices to be written to.</param>
        public void DrawFrame( int frameIndex, Vector2d [] position, bool flipX, bool flipY,
            int outArrayStartIndex, VertexTypeList.PositionDiffuse2DTexture1[] outArray )
        {
            Debug.Assert( position.Length == 4 );

            // Make sure this is a parallelogram
            Debug.Assert( ( position[1] - position[0] ).EpsilonEquals( position[2] - position[3] ) );
            Debug.Assert( ( position[3] - position[0] ).EpsilonEquals( position[2] - position[1] ) );
                          
            Frame frame = _frames[frameIndex];

            if ( frame.IsEmpty )
                return;

            Vector2d widthVector = position[1] - position[0];
            Vector2d heightVector = position[3] - position[0];

            Vector2d relOffsetXVector;
            Vector2d relWidthVector;
            

            if ( !flipX )
            {
                relOffsetXVector = widthVector * frame.RelativeOffset.X;
                relWidthVector = widthVector * frame.RelativeSize.X;
            }
            else
            {
                relOffsetXVector = widthVector - widthVector * frame.RelativeOffset.X;
                relWidthVector = widthVector * -frame.RelativeSize.X;
            }

            Vector2d relOffsetYVector;
            Vector2d relHeightVector;

            if ( !flipY )
            {
                relOffsetYVector = heightVector * frame.RelativeOffset.Y;
                relHeightVector = heightVector * frame.RelativeSize.Y;
            }
            else
            {
                relOffsetYVector = heightVector - heightVector * frame.RelativeOffset.Y;
                relHeightVector = heightVector * -frame.RelativeSize.Y;
            }

            Vector2d ul = position[0] + relOffsetXVector + relOffsetYVector;
            Vector2d ur = ul + relWidthVector;
            Vector2d lr = ur + relHeightVector;
            Vector2d ll = ul + relHeightVector;

            int outIndex = outArrayStartIndex;
            outArray[outIndex].Position.X = ul.X;
            outArray[outIndex].Position.Y = ul.Y;
            outArray[outIndex].TextureCoordinates.X = frame.TexCoords.Left;
            outArray[outIndex].TextureCoordinates.Y = frame.TexCoords.Top;

            ++outIndex;

            outArray[outIndex].Position.X = ur.X;
            outArray[outIndex].Position.Y = ur.Y;
            outArray[outIndex].TextureCoordinates.X = frame.TexCoords.Right;
            outArray[outIndex].TextureCoordinates.Y = frame.TexCoords.Top;

            ++outIndex;

            outArray[outIndex].Position.X = lr.X;
            outArray[outIndex].Position.Y = lr.Y;
            outArray[outIndex].TextureCoordinates.X = frame.TexCoords.Right;
            outArray[outIndex].TextureCoordinates.Y = frame.TexCoords.Bottom;

            ++outIndex;

            outArray[outIndex].Position.X = ll.X;
            outArray[outIndex].Position.Y = ll.Y;
            outArray[outIndex].TextureCoordinates.X = frame.TexCoords.Left;
            outArray[outIndex].TextureCoordinates.Y = frame.TexCoords.Bottom;
        }

        /// <summary>
        /// Writes position and texcoord data to the given vertices.
        /// </summary>
        /// <param name="frameIndex">The index of the frame to draw.</param>
        /// <param name="position">An array containing the 4 world vertex-positions.</param>
        /// <param name="clipArea">Clip area in local coordinates.</param>
        /// <param name="outArrayStartIndex">First array index that will be written to.</param>
        /// <param name="outArray">An array containing vertices to be written to.</param>
        public void DrawFrame( int frameIndex, Vector2d[] position, bool flipX, bool flipY,
            RectangleF clipArea, int outArrayStartIndex, 
            VertexTypeList.PositionDiffuse2DTexture1[] outArray )
        {
            Debug.Assert( position.Length == 4 );
            // Make sure this is a parallelogram
            Debug.Assert( ( position[1] - position[0] ).EpsilonEquals( position[2] - position[3] ) );
            Debug.Assert( ( position[3] - position[0] ).EpsilonEquals( position[2] - position[1] ) );

            Frame frame = _frames[frameIndex];

            if ( frame.IsEmpty )
                return;

            RectangleF intersection = new RectangleF( 
                frame.RelativeOffset.X,
                frame.RelativeOffset.Y,
                frame.RelativeSize.X,
                frame.RelativeSize.Y 
                );

            intersection.Intersect( clipArea );

            if ( intersection.IsEmpty )
                return;

            Vector2d widthVector = position[1] - position[0];
            Vector2d heightVector = position[3] - position[0];

            Vector2d relOffsetXVector;
            Vector2d relWidthVector;
            
            if ( !flipX )
            {
                relOffsetXVector = widthVector * intersection.X;
                relWidthVector = widthVector * intersection.Width;
            }
            else
            {
                relOffsetXVector = widthVector - widthVector * intersection.X;
                relWidthVector = widthVector * -intersection.Width;
            }

            Vector2d relHeightVector;
            Vector2d relOffsetYVector;

            if ( !flipY )
            {
                relOffsetYVector = heightVector * intersection.Y;
                relHeightVector = heightVector * intersection.Height;
            }
            else 
            {
                relOffsetYVector = heightVector - heightVector * intersection.Y;
                relHeightVector = heightVector * -intersection.Height;
            }

            Vector2d ul = position[0] + relOffsetXVector + relOffsetYVector;
            Vector2d ur = ul + relWidthVector;
            Vector2d lr = ur + relHeightVector;
            Vector2d ll = ul + relHeightVector;

            float texCoordLeft;
            float texCoordRight;
            float texCoordTop;
            float texCoordBottom;

            // Calculate texCoordLeft
            if ( clipArea.X <= frame.RelativeOffset.X )
            {
                texCoordLeft = frame.TexCoords.Left;
            }
            else
            {
                float f = ( ( clipArea.X - frame.RelativeOffset.X ) / frame.RelativeSize.X );
                texCoordLeft = ( f * frame.TexCoords.Width ) + frame.TexCoords.X;
            }

            // Calculate texCoordRight
            if ( clipArea.Right >= frame.RelativeOffset.X + frame.RelativeSize.X )
            {
                texCoordRight = frame.TexCoords.Right;
            }
            else
            {
                float f = ( ( clipArea.Right - frame.RelativeOffset.X ) / frame.RelativeSize.X );
                texCoordRight = ( f * frame.TexCoords.Width ) + frame.TexCoords.X;
            }

            // Calculate texCoordTop
            if ( clipArea.Y <= frame.RelativeOffset.Y )
            {
                texCoordTop = frame.TexCoords.Top;
            }
            else
            {
                float f = ( ( clipArea.Y - frame.RelativeOffset.Y ) / frame.RelativeSize.Y );
                texCoordTop = ( f * frame.TexCoords.Height ) + frame.TexCoords.Y;
            }

            // Calculate texCoordBottom
            if ( clipArea.Bottom >= frame.RelativeOffset.Y + frame.RelativeSize.Y )
            {
                texCoordBottom = frame.TexCoords.Bottom;
            }
            else
            {
                float f = ( ( clipArea.Bottom - frame.RelativeOffset.Y ) / frame.RelativeSize.Y );
                texCoordBottom = ( f * frame.TexCoords.Height ) + frame.TexCoords.Y;
            }

            int outIndex = outArrayStartIndex;
            outArray[outIndex].Position.X = ul.X;
            outArray[outIndex].Position.Y = ul.Y;
            outArray[outIndex].TextureCoordinates.X = texCoordLeft;
            outArray[outIndex].TextureCoordinates.Y = texCoordTop;

            ++outIndex;

            outArray[outIndex].Position.X = ur.X;
            outArray[outIndex].Position.Y = ur.Y;
            outArray[outIndex].TextureCoordinates.X = texCoordRight;
            outArray[outIndex].TextureCoordinates.Y = texCoordTop;

            ++outIndex;

            outArray[outIndex].Position.X = lr.X;
            outArray[outIndex].Position.Y = lr.Y;
            outArray[outIndex].TextureCoordinates.X = texCoordRight;
            outArray[outIndex].TextureCoordinates.Y = texCoordBottom;

            ++outIndex;

            outArray[outIndex].Position.X = ll.X;
            outArray[outIndex].Position.Y = ll.Y;
            outArray[outIndex].TextureCoordinates.X = texCoordLeft;
            outArray[outIndex].TextureCoordinates.Y = texCoordBottom;
        }

        /// <summary>
        /// Takes the source image, packs the requested areas in a texture.
        /// </summary>
        /// <remarks>
        /// 
        /// </remarks>
        /// <param directoryName="sourceImage">The source image</param>
        /// <param directoryName="frameAreas">The frames</param>
        /// <param directoryName="sizeHint">An optional size hint for the atlas texture</param>
        void _packImage( Bitmap sourceImage, IEnumerable<Rectangle> frameAreas, Size? sizeHint )
        {
            Bitmap destImage = null;
            List<Frame> frames = new List<Frame>();

            try
            {
                _findTransparentAreas( sourceImage, frameAreas, frames );

                // Calculate the image size
                _atlasSize = ( sizeHint.HasValue ? sizeHint.Value : _calculateSize( frames ) );

                destImage = new Bitmap( _atlasSize.Width, _atlasSize.Height, PixelFormat.Format32bppArgb );

                Graphics g = Graphics.FromImage( destImage );
                g.Clear( Color.FromArgb( 0, 0, 0, 0 ) );
                g.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.None;
                g.InterpolationMode = System.Drawing.Drawing2D.InterpolationMode.NearestNeighbor;
                g.CompositingMode = System.Drawing.Drawing2D.CompositingMode.SourceCopy;

                EngineOfEvermore.Imaging.ImageTree tree = new EngineOfEvermore.Imaging.ImageTree( _atlasSize );

                int j = 0;
                foreach ( Frame frame in frames )
                {
                    if ( !frame.IsEmpty )
                    {
                        Rectangle paddedArea = frame.OriginalNonTransparentArea;
                        paddedArea.Inflate( 1, 1 );

                        Rectangle paddedConvertedArea =
                            tree.Add( "aa", paddedArea.Size );

                        Debug.Assert( paddedConvertedArea != Rectangle.Empty );

                        frame.ConvertedArea.X = paddedConvertedArea.X + 1;
                        frame.ConvertedArea.Y = paddedConvertedArea.Y + 1;
                        frame.ConvertedArea.Width = paddedConvertedArea.Width - 2;
                        frame.ConvertedArea.Height = paddedConvertedArea.Height - 2;

                        frame.Offset.X = frame.OriginalNonTransparentArea.X - frame.OriginalArea.X;
                        frame.Offset.Y = frame.OriginalNonTransparentArea.Y - frame.OriginalArea.Y;

                        Vector2d ul = new Vector2d();
                        Vector2d ur = new Vector2d();
                        Vector2d lr = new Vector2d();
                        Vector2d ll = new Vector2d();

                        ul.X = (float) frame.ConvertedArea.Left / (float) _atlasSize.Width;
                        ul.Y = (float) frame.ConvertedArea.Top / (float) _atlasSize.Height;

                        ur.X = (float) frame.ConvertedArea.Right / (float) _atlasSize.Width;
                        ur.Y = (float) frame.ConvertedArea.Top / (float) _atlasSize.Height;

                        lr.X = (float) frame.ConvertedArea.Right / (float) _atlasSize.Width;
                        lr.Y = (float) frame.ConvertedArea.Bottom / (float) _atlasSize.Height;

                        ll.X = (float) frame.ConvertedArea.Left / (float) _atlasSize.Width;
                        ll.Y = (float) frame.ConvertedArea.Bottom / (float) _atlasSize.Height;

                        frame.TexCoords.X = ul.X;
                        frame.TexCoords.Y = ul.Y;
                        frame.TexCoords.Width = ur.X - ul.X;
                        frame.TexCoords.Height = ll.Y - ul.Y;
                        
                        frame.RelativeSize.X = (float) frame.ConvertedArea.Width / (float) frame.OriginalArea.Width;
                        frame.RelativeSize.Y = (float) frame.ConvertedArea.Height / (float) frame.OriginalArea.Height;

                        frame.RelativeOffset.X = (float) frame.Offset.X / (float) frame.OriginalArea.Width;
                        frame.RelativeOffset.Y = (float) frame.Offset.Y / (float) frame.OriginalArea.Height;

                        _drawImageToAtlas( frame, sourceImage, g );

                        //destImage.Save( "atlas" + j + ".png", ImageFormat.Png );

                        ++j;
                    }
                }

                _texture = GorgonLibrary.Graphics.Image.FromBitmap( ResourceName, destImage );

                foreach ( Frame frame in frames )
                {
                    frame.Image = _texture;
                }

                _frames = frames;

                destImage.Save( "Packed." + Path.GetFileName( ResourceName ) + ".png", 
                    ImageFormat.Png );
            }
            catch ( ArgumentException e )
            {
                // log error
                Log.Error( e.Message );
            }
            catch ( OverflowException e )
            {
                // log error
                Log.Error( e.Message );
            }
            finally
            {
                if ( sourceImage != null )
                {
                    sourceImage.Dispose();
                }

                if ( destImage != null )
                {
                    destImage.Dispose();
                }
            }
        }

        static void _findTransparentAreas( Bitmap sourceImage, 
            IEnumerable<Rectangle> frameAreas, List<Frame> frames )
        {
            // Calculate all non-transparent areas
            foreach ( Rectangle area in frameAreas )
            {
                Frame frame = new Frame();
                frame.OriginalArea = area;
                frame.OriginalNonTransparentArea =
                    _getNonTransparentArea( sourceImage, area );

                frame.IsEmpty = frame.OriginalNonTransparentArea.IsEmpty;

                frames.Add( frame );
            }
        }

        /// <summary>
        /// Calculates the minimal image size that can contained all the given frames.
        /// </summary>
        static Size _calculateSize( List<Frame> frames )
        {
            Size imageSize = new Size( 32, 32 );
            bool incX = true;

            bool repeat = true;
            while ( repeat )
            {
                try
                {
                    EngineOfEvermore.Imaging.ImageTree tree = new EngineOfEvermore.Imaging.ImageTree( imageSize );

                    int j = 0;
                    foreach ( Frame frame in frames )
                    {
                        if ( !frame.IsEmpty )
                        {
                            Size size = frame.OriginalNonTransparentArea.Size;
                            size.Width += 2;
                            size.Height += 2;

                            Rectangle rect =
                                tree.Add( "aa", size );

                            if ( rect.IsEmpty )
                                throw new OverflowException();

                            j++;
                        }
                    }

                    repeat = false;
                }
                catch ( OverflowException )
                {
                    if ( incX )
                    {
                        imageSize.Width = imageSize.Width * 2;
                    }
                    else
                    {
                        imageSize.Height = imageSize.Height * 2;
                    }

                    incX = !incX;
                }
            }

            return imageSize;
        }

        /// <summary>
        /// Finds the smallest rectangle in an area of the source image that contains all
        /// non-transparent pixels.
        /// </summary>
        static Rectangle _getNonTransparentArea( Bitmap src, Rectangle area )
        {
            Debug.Assert( new Rectangle( 0, 0, src.Width, src.Height ).Contains( area ) );

            int minX = int.MaxValue;
            int minY = int.MaxValue;
            int maxX = int.MinValue;
            int maxY = int.MinValue;

            for ( int y = area.Top; y < area.Bottom; ++y )
                for ( int x = area.Left; x < area.Right; ++x )
                {
                    Color color = src.GetPixel( x, y );

                    if ( color.A != 0 )
                    {
                        if ( x < minX )
                            minX = x;

                        if ( x > maxX )
                            maxX = x;

                        if ( y < minY )
                            minY = y;

                        if ( y > maxY )
                            maxY = y;
                    }
                }

            if ( minX > maxX )
            {
                return new Rectangle( 0, 0, 0, 0 );
            }
            else
            {
                return new Rectangle( minX, minY, maxX - minX + 1, maxY - minY + 1 );
            }
        }

        /// <summary>
        /// Draws a frame to the atlas texture, including the padding of 1 pixel
        /// </summary>
        /// <param directoryName="frame">The frame to draw to the atlas</param>
        /// <param directoryName="src">The source image containing the original frame</param>
        /// <param directoryName="g">The Graphics object wrapping the atlas texture</param>
        static void _drawImageToAtlas( Frame frame, System.Drawing.Image src, Graphics g )
        {
            g.DrawImage( src, frame.ConvertedArea,
                frame.OriginalNonTransparentArea, GraphicsUnit.Pixel );

            Rectangle padDest = new Rectangle();
            Rectangle padSrc = new Rectangle();

            padDest.X = frame.ConvertedArea.X - 1;
            padDest.Y = frame.ConvertedArea.Y;
            padDest.Width = 1;
            padDest.Height = frame.ConvertedArea.Height;

            padSrc.X = frame.OriginalNonTransparentArea.X;
            padSrc.Y = frame.OriginalNonTransparentArea.Y;
            padSrc.Width = 1;
            padSrc.Height = frame.OriginalNonTransparentArea.Height;

            g.DrawImage( src, padDest, padSrc, GraphicsUnit.Pixel );

            padDest.X = frame.ConvertedArea.Right;
            padSrc.X = frame.OriginalNonTransparentArea.Right - 1;

            g.DrawImage( src, padDest, padSrc, GraphicsUnit.Pixel );

            padDest.X = frame.ConvertedArea.X;
            padDest.Y = frame.ConvertedArea.Y - 1;
            padDest.Width = frame.ConvertedArea.Width;
            padDest.Height = 1;

            padSrc.X = frame.OriginalNonTransparentArea.X;
            padSrc.Y = frame.OriginalNonTransparentArea.Y;
            padSrc.Width = frame.OriginalNonTransparentArea.Width;
            padSrc.Height = 1;

            g.DrawImage( src, padDest, padSrc, GraphicsUnit.Pixel );

            padDest.Y = frame.ConvertedArea.Bottom;
            padSrc.Y = frame.OriginalNonTransparentArea.Bottom - 1;

            g.DrawImage( src, padDest, padSrc, GraphicsUnit.Pixel );
        }

        protected override void _dispose( bool disposing )
        {
            if ( !_disposed )
            {
                if ( disposing )
                {
                    if ( _texture != null )
                    {
                        _texture.Dispose();
                    }
                }

                _texture = null;

                if ( _frames != null )
                {
                    foreach ( Frame frame in _frames )
                    {
                        frame.Image = null;
                    }
                }

                _disposed = true;
            }

            base._dispose( disposing );
        }

        public static Type[] GetFrameGeneratorTypes()
        {
            if ( _frameGeneratorTypes != null )
            {
                return _frameGeneratorTypes.ToArray();
            }

            _frameGeneratorTypes = new List<Type>();

            Assembly[] assemblies = AppDomain.CurrentDomain.GetAssemblies();

            foreach ( Assembly asm in assemblies )
            {
                Type[] types = asm.GetExportedTypes();

                foreach ( Type t in types )
                {
                    if ( t.GetInterfaces().Contains( typeof( IFrameGenerator ) ) )
                    {
                        _frameGeneratorTypes.Add( t );
                    }
                }
            }

            return _frameGeneratorTypes.ToArray();
        }

        public static IFrameGenerator CreateFrameGenerator( String xmlName )
        {
            if ( _xmlNameToframeGeneratorType == null )
            {
                _xmlNameToframeGeneratorType = new Dictionary<string, Type>();

                Type[] frameGeneratorTypes = GetFrameGeneratorTypes();

                foreach ( Type type in frameGeneratorTypes )
                {
                    Object inst = TypeDescriptor.CreateInstance( null, type, null, null );
                    IFrameGenerator frameGenerator = (IFrameGenerator) inst;

                    _xmlNameToframeGeneratorType.Add( 
                        frameGenerator.XmlName, 
                        type 
                        );
                }
            }

            Type t;

            if ( _xmlNameToframeGeneratorType.TryGetValue( xmlName, out t ) )
            {
                Object inst = TypeDescriptor.CreateInstance( null, t, null, null );
                return (IFrameGenerator) inst;
            }
            else
            {
                throw new Exception( "Name " + xmlName + " not registered." );
            }
        }

        static List<Type> _frameGeneratorTypes;
        static Dictionary<String, Type> _xmlNameToframeGeneratorType;

        #endregion
    }
}
